Mesh networks are 802.11-based multi-hop wireless backbones that provide low-cost Internet access in urban areas. Crucial to the performance of mesh networks is the routing protocol operation, and significant research effort has been devoted to metrics that identify high quality paths. First, it was shown that link cost metrics that estimate link quality by periodic probing can compose path metrics that yield significant throughput gains over minimum hop count (D. D. Couto, D. Aguayo, J. Bicket, and R. Morris, “A high-throughput path metric for multi-hop wireless routing” in Proc. MobiCom, 2003). Further throughput improvements have been achieved by link cost and path metrics that incorporate multi-channel diversity (R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks” in Proc. MobiCom, 2004), interference (A. Subramanian, M. Buddhikot, and S. Miller, “Interference Aware Routing in Multi-radio Wireless Mesh Networks” in Proc. WiMe 2006 and Y. Yang, J. Wang, and R. Kravets, “Interference-aware load balancing for multihop wireless networks” University of Illinois at Urbana-Champaign, Tech. Rep., 2005), or congestion (T. Salonidis, M. Garetto, A. Saha, and E. Knightly, “Identifying Highthroughput Paths in 802.11 Mesh Networks: a Model-based Approach” in Proc. ICNP, 2007). Path metrics are typically evaluated in terms of their static properties by running separate back-to-back experiments under identical traffic patterns and comparing UDP or TCP throughput (R. Draves, J. Padhye, and B. Zill, “Comparison of Routing Metrics Static Multi-hop Wireless Networks” in Proc. SIGCOMM, 2004 and Y. Yang, J. Wang, and R. Kravets, “Designing Routing Metrics for Mesh Networks” Proc. WiMesh, 2005).
Despite extensive work on path metrics, the ability of the underlying link cost metrics to accurately estimate wireless link quality under dynamic conditions has not yet been quantified. Link cost metrics are inherently inaccurate because, instead of a direct measure like throughput or delay, they only estimate an indirect measure of link quality using a limited number of probe packets. The ability of a link cost metric to estimate link quality depends both on its definition and on its measurement method. Quantifying this ability is crucial to the performance of the mesh routing protocol, especially under dynamic operation. If a link cost metric does not track the variation of link quality, the routing algorithm cannot react properly. On the other hand, if a link cost metric varies while the link quality does not, the routing algorithm will take unnecessary or erroneous actions. Previous studies of link cost metric dynamics (A. Subramanian, M. Buddhikot, and S. Miller, “Interference Aware Routing in Multi-radio Wireless Mesh Networks” in Proc. WiMe 2006 and S. Das, H. Pucha, K. Papagianakki, and Y.-C. Hu, “Studying wireless routing link metric dynamics” in Proc. IMC, 2007) have observed sensitivity to network traffic but do not connect metric variations to variations of a direct measure of link quality.
Examples of the methodology applied by previous works follow.
De Couto et al. (D. D. Couto, D. Aguayo, J. Bicket, and R. Morris, “A high-throughput path metric for multi-hop wireless routing,” in Proc. MobiCom, 2003) propose ETX as link cost and path metric. They study the accuracy of ETX (as a link metric) by comparing it to the number of retransmissions experienced by UDP packets. These two quantities are measured at different points in time (one minute apart), and for a very short duration (1 second and 10 seconds, respectively). Although the authors list some of the weaknesses of this estimation technique, they do not quantify the impact of these shortcomings. In contrast, the inventors of the present invention compare simultaneously estimated quantities, and show how different shortcomings manifest in the metrics' correlation to the link capacity.
Draves et al. (R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio, multi-hop wireless mesh networks” in Proc. MobiCom, 2004) propose ETT, a link cost metric, and WCETT, a routing metric. They do not study the accuracy of ETT as link metric, but study the accuracy of the estimation of the link's bit-rate by the packet pair technique. However, their evaluation is limited to two nodes in close proximity, and this experimental setting suppresses the shortcomings of this technique since the number of retransmissions is likely to be small and stable. In contrast, the work, by the inventors of the present invention, that lead to the present invention covers a large set of links with different characteristics, and consequently provides a more realistic evaluation.
Das et al. (S. Das, H. Pucha, K. Papagianakki, and Y.-C. Hu, “Studying wireless routing link metric dynamics” in Proc. IMC, 2007) study three link cost metrics: ETX, ETT and the links bandwidth estimated by the packet pair technique. They investigate the link metrics' dynamic behavior and their sensitivity to traffic in the network. However, they do not quantify the accuracy of these link metrics and do not correlate to the variation of a direct measure of the link's quality. Subramanian et al. (A. Subramanian, M. Buddhikot, and S. Miller, “Interference Aware Routing in Multi-radio Wireless Mesh Networks” in Proc. WiMe 2006) propose iAWARE, a link and routing metric. The link version of iAWARE is compared to ETT and IRU (Y. Yang, J. Wang, and R. Kravets, “Interference-aware load balancing for multihop wireless networks” University of Illinois at Urbana-Champaign, Tech. Rep., 2005) in one controlled scenario to show the poor interference awareness of ETT and IRU.
Kim and Shin (K.-H. Kim and K. Shin, “On accurate measurement of link quality multi-hop wireless mesh networks” in Proc. MobiCom, 2006) propose a complex probing system (EAR), which relies on the standard MAC MIB interface to query the driver for MAC layer statistics. This work is complementary to the work performed by the inventors of the present invention and this system may be used to retrieve the cross layer information used by the method according to the present invention. They study the accuracy of the estimation of the frame delivery ratio by several approaches. However, the compared estimations are taken at different points in time. On the contrary, one fundamental aspect of the method according to the present invention is the comparison of simultaneous measurements.
Draves et al. (R. Draves, J. Padhye, and B. Zill, “Comparison of Routing Metrics Static Multi-hop Wireless Networks” in Proc. SIGCOMM, 2004) compare four path metrics: Hop Count, Per-hop Round Trip Time, Per-hop Packet Pair Delay, and ETX. Yang et al (Y. Yang, J. Wang, and R. Kravets, “Interference-aware load balancing for multihop wireless networks” University of Illinois at Urbana-Champaign, Tech. Rep., 2005) propose the MIC path metric which relies on several link's characteristics, including ETT. Both these work present and compare path metrics, focusing on the performance and characteristics of the discovered routing paths. However, neither the behavior nor the accuracy of the underlying link cost metric has been evaluated.